package br.unifor.lec.aco.graph;

import java.util.ArrayList;
import java.util.List;

import br.unifor.lec.aco.Parameters;

//atualizacao
public class Grafo {

	private float[][] incidenceMatrix;
	private Vertice[] vertices;

	public Grafo(Vertice[] vertices) {
		this.vertices = vertices;
		calculateDistances();
		Parameters p = new Parameters();
		if (p.usarHeuristica)
			calculeteDIndex();
		else
			calculeteDIndexUm();
	}

	public void calculeteDIndex() {
		System.out.println("Calculando heuristica atraves de Bellman-Ford..");
		BellmanFord();
		System.out.println("Fim do calculo!");
	}

	public ArrayList<Vertice> getTargets() {
		ArrayList<Vertice> targets = new ArrayList<Vertice>();
		for (int i = 0; i < this.getNumVertices(); i++) {
			if (vertices[i].target) {
				targets.add(vertices[i]);
			}
		}
		return targets;
	}

	public void BellmanFord() {
		ArrayList<Vertice> targets = new ArrayList<Vertice>();
		targets = getTargets();

		for (int w = 0; w < this.getNumVertices(); w++) {
			Vertice v = vertices[w];

			// Passo 1 : Inicializar grafo
			for (int l = 0; l < this.getNumVertices(); l++) {
				vertices[l].distanciaBM = Float.MAX_VALUE;
				vertices[l].anteriorBM = null;
			}
			v.distanciaBM = 0;

			// Passo 2: Ajustar arestas repetidamente
			for (int i = 0; i < vertices.length; i++) { // repita tamanho de arestas vezes
				for (int j = 0; j < vertices.length; j++) {
					Vertice temp = vertices[j];
					for (int k = 0; k < temp.adjacents.size(); k++) { // pra cada aresta do grafo
						Vertice tempK = vertices[temp.adjacents.get(k)];
						double sdf = incidenceMatrix[j][temp.adjacents.get(k)];
						if (tempK.distanciaBM > temp.distanciaBM
								+ sdf) {
							tempK.distanciaBM = temp.distanciaBM
									+ incidenceMatrix[j][temp.adjacents.get(k)];
							tempK.anteriorBM = "" + j;
						}
					}
				}
			}
			// Passo 3 : Verificar a existencia de ciclos com peso negativo
			for (int j = 0; j < vertices.length; j++) {
				Vertice tempi = vertices[j];
				for (int k = 0; k < tempi.adjacents.size(); k++) { // pra cada aresta do grafo
					Vertice tempK = vertices[tempi.adjacents.get(k)];
					if (tempK.distanciaBM > tempi.distanciaBM
							+ incidenceMatrix[j][tempi.adjacents.get(k)])
						System.out.println("Erro: grafo com ciclo de peso negativo!");
				}
			}
			// Calculando D
			float somatotalInversoD = 0;
			float somatotal = 0;
			for (Vertice target : targets) {
				somatotalInversoD += 1 / target.distanciaBM;
				somatotal += target.distanciaBM;
			}
			v.distanciaAlvos = somatotal;
			v.d = somatotalInversoD;
		}
	}

	private void calculateDistances() {
		incidenceMatrix = new float[vertices.length][vertices.length];
		for (int i = 0; i < vertices.length; i++) {
			List<Integer> adjacents = vertices[i].adjacents;
			for (int j = 0; j < adjacents.size(); j++) {
				if (adjacents.get(j) > i) {
					incidenceMatrix[i][adjacents.get(j)] = euclidianDistance(i, adjacents.get(j));
				} else {
					incidenceMatrix[i][adjacents.get(j)] = incidenceMatrix[adjacents.get(j)][i];
				}
			}
		}
	}

	private float euclidianDistance(int i, int j) {
		Vertice vi, vj;
		vi = vertices[i];
		vj = vertices[j];
		return (float) Math.sqrt(Math.pow(vi.x - vj.x, 2) + Math.pow(vi.y - vj.y, 2));
	}

	private void calculeteDIndexUm() {
		for (Vertice v : vertices) {
			v.d = 1;
		}
	}

	public float[][] getIncidenceMatrix() {
		return incidenceMatrix;
	}

	public Vertice[] getVertices() {
		return vertices;
	}

	public int getNumVertices() {
		return vertices.length;
	}
}